// 216. 组合总和 III
// 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

// 只使用数字1到9
// 每个数字 最多使用一次 
// 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
// 示例 1:

// 输入: k = 3, n = 7
// 输出: [[1,2,4]]
// 解释:
// 1 + 2 + 4 = 7
// 没有其他符合的组合了。
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
 var combinationSum3 = function(k, n) {
    let res=[];
    let ans=[];
    const def=function(k,n,cur,sum){
        if(ans.length==k){
            if(sum==n){
                res.push([...ans]);
            }
            return;// 如果path.length == k 但sum != n 直接返回
        }
        for(let i=cur;i<=9;i++){// 范围为1-9
            sum+=i;
            ans.push(i);
            def(k,n,i+1,sum);
            sum-=i;// 回溯
            ans.pop();// 回溯
        }
    }
    def(k,n,1,0);
    return res;
};

// 39. 组合总和
// 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
// 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
// 并以列表形式返回。你可以按 任意顺序 返回这些组合。

// candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，
// 则两种组合是不同的。 

// 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
// 示例 1：

// 输入：candidates = [2,3,6,7], target = 7
// 输出：[[2,2,3],[7]]
// 解释：
// 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
// 7 也是一个候选， 7 = 7 。
// 仅有这两种组合。
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
 var combinationSum = function(candidates, target) {
    const res=[],ans=[];
    candidates.sort((a,b)=>a-b);// 排序
    // 需要startIndex来控制for循环的起始位置
    const backtracking=function(candidates,target,sum,start){
        // 终止只有两种情况，sum大于target和sum等于target
        if(sum>target){
            return;
        }
        // sum等于target的时候，需要收集结果
        if(sum==target){
            res.push(Array.from(ans));
            return;
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for(let i=start;i<candidates.length&&sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            ans.push(candidates[i]);
            backtracking(candidates,target,sum,i);
            sum-=candidates[i];
            ans.pop();
        }
    }
    backtracking(candidates,target,0,0);
    return res;
};

// 40. 组合总和 II(去重)
// 给定一个候选人编号的集合 candidates 和一个目标数 target ，
// 找出 candidates 中所有可以使数字和为 target 的组合。

// candidates 中的每个数字在每个组合中只能使用 一次 。

// 注意：解集不能包含重复的组合。 

// 示例 1:

// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 输出:
// [
// [1,1,6],
// [1,2,5],
// [1,7],
// [2,6]
// ]
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
 var combinationSum2 = function(candidates, target) {
    const res=[];
    const ans=[];
    candidates.sort((a,b)=>a-b);
    let used = new Array(candidates.length).fill(false);
    const backtracking=function(sum,start){
        if(sum>target){
            return;
        }
        if(sum==target){
            res.push([...ans]);
        }
        for(let i=start;i<candidates.length&&sum<=target;i++){
            const cur = candidates[i];
            // 如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，
            // 就说明：前一个树枝，使用了candidates[i - 1]，
            // 也就是说同一树层使用过candidates[i - 1]。
            // 因为两个数相同，所产生的结果也相同 所以跳过 不要重复读取
            if ( i > 0 && cur === candidates[i - 1] && !used[i - 1])
                   continue;
            // if (i > start && candidates[i] == candidates[i - 1]) {
            //         continue;
            //     } 直接使用start去重也可以
            sum+=candidates[i];
            ans.push(candidates[i]);
            used[i]=true;
            backtracking(sum,i+1);
            sum-=candidates[i];
            used[i]=false;
            ans.pop();
        }
    }
    backtracking(0,0);
    return res;
};